1. Field of the Invention
This invention related to the field of memory management and more particularly to heap compaction.
2. Description of the Related Art
In the field of computer systems, considerable effort has been expended on the task of allocating and managing memory. In general, memory may be allocated to data objects (which may also be referred to as data structures or records) either statically or dynamically. Some computer languages may require that memory be allocated for all the variables defined in a program statically, e.g., at compile time. Such static memory allocation may make it difficult to share available memory space among multiple applications, especially for applications that are long-lived. Abiding by space limitations may be easier when the platform provides support for dynamic memory allocation, i.e., when memory space to be allocated to a given object is determined at run time.
Particularly for long-lived applications, though, allocation and reclamation of dynamic memory must be performed carefully. If the application fails to reclaim unused memory—or, worse, loses track of the address of a dynamically allocated segment of memory—its memory requirements may grow over time to exceed the system's available memory. This kind of error is known as a “memory leak.” Another kind of error occurs when an application reclaims memory for reuse even though it still maintains a reference to that memory. If the reclaimed memory is reallocated for a different purpose, the application may inadvertently manipulate the same memory in multiple inconsistent ways. This kind of error is known as a “dangling reference.”
One way of reducing the likelihood of such leaks and related errors is to provide memory-space reclamation in a more automatic manner. Techniques used by systems that reclaim memory space automatically are commonly referred to as garbage collection. Garbage collectors operate by reclaiming space that they no longer consider “reachable.” Statically allocated objects represented by a program's global variables are normally considered reachable throughout a program's life. Such objects are not ordinarily stored in the garbage collector's managed memory space, but they may contain references to dynamically allocated objects that are, and such objects are considered reachable. Clearly, an object referred to in the processor's call stack is reachable, as is an object referred to by register contents. And an object referred to by any reachable object is also reachable.
Various parts and levels of a computing system can implement garbage collection. One approach is simply to provide garbage collection as part of a batch compiler's output. In this approach to garbage collection, in addition to generating code for the functionality supported by an application, the batch compiler may generate code that automatically reclaims unreachable memory space without explicit direction from a the programmer, and include it within the application's object code. Even in this simple case, though, there is a sense in which the application does not itself provide the entire garbage collector. Specifically, the application will typically call upon the underlying operating system's memory-allocation functions. And the operating system may in turn take advantage of various hardware that lends itself particularly to use in garbage collection. So even a very simple system may disperse the garbage collection mechanism over a number of computer system layers.
Another approach to garbage collection may be taken in some systems that employ “virtual machines”. In such a system, a compiler or an interpreter may convert source code for an application from a high-level language to instructions called “byte code” for virtual machines that various processors can be configured to emulate. One example of a high-level language for which compilers and interpreters are available to produce such virtual-machine instructions is the Java™ programming language. (Java is a trademark or registered trademark of Sun Microsystems, Inc., in the United States and other countries.) Typically, byte-code routines are executed by a processor under control of a virtual-machine process, and the virtual machine process provides memory management functions including garbage collection. For example, a memory management component of the virtual machine process may be responsible for allocating memory dynamically as needed and reclaiming unreachable memory when possible. Various other approaches to garbage collection may be employed, including implementation of garbage collection functions in hardware.
In distinguishing reachable objects from unreachable objects, garbage collectors often have to trace references between objects—for example, some garbage collectors have to identify those reference fields of an object that have been modified, as well as the objects that are referred to in the modified fields. In order to limit the amount of analysis required for collection, a record or trace of objects whose references have been modified may be maintained.
Garbage collection schemes, such as mark-sweep and reference-counting garbage collection techniques, are generally susceptible to fragmentation, where the heap includes more and more gaps between active, live objects. As a heap becomes more fragmented, it may become more and more difficult to allocate large spans of memory. To avoid this fragmentation problem, many garbage collectors compact the heap periodically to remove some or all of the gaps between live memory objects. Compacting a heap may coalesce the gaps into a single, contiguous block of memory, thereby allowing for larger objects to be allocated.
There are a number of traditional approaches to heap compaction. For example, one is to compact all reachable object to one end of the address range of the heap. Because groups of objects are moved in address order, this technique is often referred to as sliding compaction. This approach works well even when objects differ in size. By preserving the ordering of objects in the heap, it allows for a simple, pointer-bumping allocation scheme. The primary obstacle to the use of sliding compaction on multiprocessors is that the act of sliding object must be carefully staged so that reachable objects are not overwritten before they can be moved to their final destinations.